<?php

class SimulatedAnnealing {

	private $temperatureStart;
	private $temperatureEnding;
	private $maxIterations;
	private $coolingFactor;
	private $universe;
	private $subsets;
	private $weights;
	private $minValue;
	private $maxValue;
	private $swapped;
	private $minLength;
	private $calculated;
	private $weighted;
	
	public function __construct($temperatureStart = 150, $coolingFactor = 0.95, $temperatureEnding = 0.01, $weighted = false) {
		$this->temperatureStart = $temperatureStart;
		$this->temperatureEnding = $temperatureEnding;
		$this->coolingFactor = $coolingFactor;
		$this->minValue = 1;
		$this->maxValue = 100;
		$this->universe = range($this->minValue, $this->maxValue, 1);
		$this->swapped = array();
		$this->minLength = 50;					// Number of subsets in set cover, needs to be n-1 in order to swap
		$this->calculated = array();
		$this->weighted = false;
	}
	
	/**
	 * For set cover we do not have fixed number of subsets
	 * In order to get the best solution, we need to give some range of different set sizes
	 */
	public function annealingIterative() {
		$bestSolutionFound = false;
		
		$current = $this->annealing();
		$best = $current;
		$this->minLength++;
		
		for ($i = $this->minLength; $i <= 51; $i++) {
			$current = $this->annealing();
			if ($this->cost($best) < $this->cost($current)) {
				$best = $current; 
							
			}
			$this->minLength++;
			
		}
				
		$this->validate($best);
		
		return $best;
	}
	
	public function annealing() {
		$temperature = $this->temperatureStart;
		$temperatureEnding = $this->temperatureEnding;
		
		$currentSetCover = $this->getInitialRandomSetCover();
		$bestSetCover = $currentSetCover;
		$costCurrent = $this->cost($currentSetCover);
		$costBest = $costCurrent;
		
		$step = 0;
		$randomStep = 0;
		
		while ($temperature > $temperatureEnding) {
			$neighborSetCover = $this->getNeighbor($currentSetCover);
			$costNeighbor = $this->cost($neighborSetCover);
			
			$delta = $costCurrent - $costNeighbor;

			$exp = exp((-$delta / $temperature));
			$randomNumber = $this->getRandomFloatingPointNumber(0, 1);
			
			if ($delta < 0 || $exp > $randomNumber) {
				$currentSetCover = $neighborSetCover;
				$costCurrent = $costNeighbor;
				
				if ($costCurrent > $costBest) {				// If we have found better set cover
					$bestSetCover = $currentSetCover;
					$costBest = $costCurrent;
				}
				$randomStep++;
			} 

			$temperature = $temperature * $this->coolingFactor;
			$step++;
		}
		
		return $bestSetCover;
	}
	
	protected function getNeighbor(array $currentSetCover) {
		$neighborIndex = rand($this->minValue, $this->maxValue);
		
		$found = false;
		if (!isset($currentSetCover[$neighborIndex])) {
			$found = true;
		}
		while (!$found) {
			$neighborIndex = rand($this->minValue, $this->maxValue);
			if (!isset($currentSetCover[$neighborIndex])) {
				$found = true;
			}
		}

		$randomSetIndex = array_rand($currentSetCover, 1);
		while ($neighborIndex == $randomSetIndex) {
			$randomSetIndex = array_rand($currentSetCover, 1);
		}

		unset($currentSetCover[$randomSetIndex]);

		$currentSetCover[$neighborIndex] = $this->subsets[$neighborIndex];
	
		return $currentSetCover;
	}
	
	protected function validate($result) {
		$uniqueElements = array();
		$errors = 0;
		foreach ($result as $i => $subset) {
			
			foreach ($subset as $value) {
				
				if (isset($uniqueElements[$value])) {
					$errors++;
				} else {
					$uniqueElements[$value] = $value;
				}
			}
		}
		
		echo 'Total: ' . count($uniqueElements) . ' (actual: 100)<br>';
		echo 'Duplicates: ' . $errors . '<br>';
		
		return (count($uniqueElements) == count($this->universe));
	}
	
	protected function getInitialRandomSetCover() {
		$setCover = $this->subsets;
		
		return $this->shuffleAssoc($setCover);
	}
	
	protected function cost(array $setCover) {
		// Merge all of the subsets
		// Count intersections
		// Count the coverability of the universe
		
		$merged = array();
		$overlappings = 0;
		
		$weights = 0;
		foreach ($setCover as $i => $subset) {
			$difference = array_intersect($merged, $subset);
			$overlappings += count($difference);
			$merged = array_merge($merged, $subset);
			$weights += $this->weights[$i];
		}
		
		$intersection = array_intersect(array_unique($merged), $this->universe);
		$cost = count($intersection);
		
		if ($this->weighted) {
			$cost = $cost / $weights;
		}
		
		return $cost - $overlappings;
	}
	
	protected function shuffleAssoc($subset) {
		$shuffled = array();
		$arrayKeys = array_keys($subset);
		shuffle($arrayKeys);
		
		$count = 0;
		foreach ($arrayKeys as $arrayKey) {
			if ($count == $this->minLength) {
				break;
			}
			
			$shuffled[$arrayKey] = $subset[$arrayKey];
			$count++;
		}
		
		
		return $shuffled;
	}
	
	public function readFile($fileName) {
		$file = fopen($fileName, 'r');
		$header = fgets($file);
		$count = 1;
		while(!feof($file)) {
			$line = fgets($file);
			$row = preg_split('/\s+/', $line);
				
			if (count($row) < 2) {
				break;
			}
			array_shift($row);
			$weight = (float) (mb_substr(array_shift($row), 2)); // Remove the "w=" part, and retrieve weight
		
			$subset = array();
			foreach ($row as $element) {
				if ($element != null) {
					$subset[] = $element;
				}
			}
				
			$this->subsets[$count] = $subset;
			$this->weights[$count] = $weight;
				
			$count++;
		}
		
		fclose($file);
	}
	
	protected function getRandomFloatingPointNumber($min, $max) {
	
		return $min + mt_rand() / mt_getrandmax() * ($max - $min);
	}
}
